package main.Q1201_1300;

public class Q1201_1210 {
    public static void main(String[] args) {
        System.out.println("Question1201：丑数Ⅲ");
        System.out.println("Question1202：");
        System.out.println("Question1203：");
        System.out.println("Question1204：");
        System.out.println("Question1205：");
        System.out.println("Question1206：");
        System.out.println("Question1207：");
        System.out.println("Question1208：");
        System.out.println("Question1209：");
        System.out.println("Question1210：");
    }
}

class Question1201{
    public int nthUglyNumber(int n, int a, int b, int c) {
        long lcm_ab = lcm(a, b);
        long lcm_bc = lcm(b, c);
        long lcm_ac = lcm(a, c);
        long lcm_abc = lcm(a, lcm(b, c));
        int min = Math.min(a, Math.min(b, c));
        long l = 0, r = min * 1L * n + 1;
        while (l + 1 < r) {
            long m = l + (r - l) / 2;
            long count = m / a + m / b + m / c - m / lcm_ab - m / lcm_ac - m / lcm_bc + m / lcm_abc;
            if (count < n) {
                l = m;
            } else {
                r = m;
            }
        }
        return (int) r;
    }

    // 求最小公倍数
    private long lcm(long a, long b) {
        return a * 1L * (b / gcd(a, b));
    }

    // 求最大公约数
    private long gcd(long a, long b) {
        return b == 0 ? a : gcd(b, a % b);
    }
}